package leetcode;


/**
 * Created by Ghost on 2014/12/18 0018.
 */
public class Maximum_Gap {

    private void sort(int start, int end, int[] num){
        if(start<end){
            int begin = start,last = end;
            int tree = num[start];
            while(start<end){
                for(;end>start && num[end]>=tree;end--);
                num[start] = num[end];
                for(;end>start && num[start]<=tree;start++);
                num[end] = num[start];
            }
            num[start] = tree;
            sort(begin,start-1,num);
            sort(start+1,last,num);
        }
    }
    public void quicksort(int[] num){
        sort(0,num.length-1,num);
    }
    public int maximumGap(int[] num) {
        if(num.length<2)
            return 0;


        quicksort(num);
        int g = 0;
        for(int i=1;i<num.length;i++)
            if(g<num[i]-num[i-1])
                g = num[i]-num[i-1];
        return g;
    }
    public static void main(String[] args){
        Maximum_Gap maximum_gap = new Maximum_Gap();
    }
}
